﻿#include <stdio.h>
#include <limits.h>
#include <strings.h>

//
// good hash table primes
//
// lwr      upr	    % err       prime
// 2^5	    2^6     10.416667   53
// 2^6      2^7     1.041667    97
// 2^7      2^8     0.520833    193
// 2^8      2^9     1.302083    389
// 2^9      2^10    0.130208    769
// 2^10     2^11    0.455729    1543
// 2^11     2^12    0.227865    3079
// 2^12     2^13    0.113932    6151
// 2^13     2^14    0.008138    12289
// 2^14     2^15    0.069173    24593
// 2^15     2^16    0.010173    49157
// 2^16     2^17    0.013224    98317
// 2^17     2^18    0.002543    196613
// 2^18     2^19    0.006358    393241
// 2^19     2^20    0.000127    786433
// 2^20     2^21    0.000318    1572869
// 2^21     2^22    0.000350    3145739
// 2^22     2^23    0.000207    6291469
// 2^23     2^24    0.000040    12582917
// 2^24     2^25    0.000075    25165843
// 2^25     2^26    0.000010    50331653
// 2^26     2^27    0.000023    100663319
// 2^27     2^28    0.000009    201326611
// 2^28     2^29    0.000001    402653189
// 2^29     2^30    0.000011    805306457
// 2^30     2^31    0.000000    1610612741

static const unsigned primes[][2] = {
    { (2^6 )-1,         53 },
    { (2^7 )-1,         97 },
    { (2^8 )-1,        193 },
    { (2^9 )-1,        389 },
    { (2^10)-1,        769 },
    { (2^11)-1,       1543 },
    { (2^12)-1,       3079 },
    { (2^13)-1,       6151 },
    { (2^14)-1,      12289 },
    { (2^15)-1,      24593 },
    { (2^16)-1,      49157 },
    { (2^17)-1,      98317 },
    { (2^18)-1,     196613 },
    { (2^19)-1,     393241 },
    { (2^20)-1,     786433 },
    { (2^21)-1,    1572869 },
    { (2^22)-1,    3145739 },
    { (2^23)-1,    6291469 },
    { (2^24)-1,   12582917 },
    { (2^25)-1,   25165843 },
    { (2^26)-1,   50331653 },
    { (2^27)-1,  100663319 },
    { (2^28)-1,  201326611 },
    { (2^29)-1,  402653189 },
    { (2^30)-1,  805306457 },
    { UINT_MAX, 1610612741 },
};

//
// strings_test - 测试值最大为 1 的位数
//
void strings_test(void) {
    int x, l;

    l = ffs(x = 7);
    printf("x = %d -> %d\n", x, l);

    l = ffs(x = 8);
    printf("x = %d -> %d\n", x, l);

    l = ffs(x = -1);
    printf("x = %d -> %d\n", x, l);

    // 下面是以后 hash 种子取值的先行军
    unsigned used = (2^6)-1;
    unsigned pidx = 0;

    unsigned benc = primes[pidx][0];
    unsigned size = primes[pidx][1];

    printf("used = %u, pidx = %u, benc = %u, cap = %u\n", 
        used, pidx, benc, size);

    if (++used > benc) {
        // 开始重新扩容
        ++pidx;
        benc = primes[pidx][0];
        size = primes[pidx][1];
    }

    printf("used = %u, pidx = %u, benc = %u, cap = %u\n", 
        used, pidx, benc, size);
}
